1. Field of the Invention
The present invention pertains to the field of computer graphics. More particularly, the present invention involves a method and apparatus for supersampling texture in a raster subsystem.
2. Related Art
Computer systems are commonly used for displaying graphical images on a display screen. A typical computer generated image is drawn from a plurality of constituent geometric primitives, i.e. polygons, points, lines and three-dimensional objects. To render a display image, each primitive must be transformed from object space to display screen space. Each input primitive may contribute to one or more pixels of the final image (a pixel is a picture element of a display means in display screen space).
Texture is added to provide richer surface detail to a display object. In texture mapping, texel data from a two-dimensional (2-D) or three-dimensional (3-D) texture map (or pattern image) is combined with an area or surface of an object to produce a modified object with the added texture detail. See, e.g., Foley et al., Computer Graphics Principles and Practice, Second Edition, Addison-Wesley Publishing Company, Reading, Mass. (1990), pp. 742-743 and 826-828 (incorporated herein by reference).
"Exact" texture mapping algorithms are known which can display a very high quality textured image. These algorithms obtain a substantially exact texture mapping by examining the contribution of every texel under a pixel footprint to an overall texel value to be mapped to the pixel footprint. In this way, texture is mapped over an entire pixel footprint for any arbitrary pixel footprint shape and orientation. See, e.g., the Feibush, Levoy, and Cook algorithm and the Blinn and Newell algorithm as summarized by Foley at pp. 742-743 and Wolberg, G., Digital Image Warping, (I.E.E.E. Computer Society Press: Los Alamitos, Calif. 1990), Chapter 6, page 178 (incorporated herein by reference).
For performance and cost reasons, however, exact mapping algorithms are often unworkable. A texture is often represented by a million or more texels. A single display scene can map from tens or hundreds of different textures. Complex video images and special effects further increase the work required for an exact texture-mapping, as the number of texels which must be processed and filtered for a single pixel footprint is driven higher. Thus, the number of calculations required in an exact mapping algorithm is simply too great to practically provide high-quality texture detail in real-time. The performance limitations of exact texture-mapping are especially acute in the display of complex images, such as video, or in special effects applications where display objects are warped, distorted, or displayed in perspective.
Approximations have been made to the pixel footprint's shape and/or orientation to map texture more economically. The loss of texture quality due to these approximations, however, is pronounced when the shape and/or orientation of the pixel footprint differs from a corresponding texel to which it is approximately mapped. Aliasing artifacts deteriorate image quality when texels are undersampled and do not adequately cover a pixel footprint area. Conversely, excessive blurriness results when too many texels are mapped to a pixel footprint due to oversampling. See, e.g., the discussion of anti-aliasing in Wolberg, Chapter 6, pages 163-186, incorporated herein by reference.
As shown in FIG. 1A, two specific orientations of a pixel footprint A relative to a texture grid, that is, rotated and in-perspective, illustrate the sampling problems encountered in texture mapping (see Wolberg at page 167). As the pixel footprint A rotates with respect to a texture grid, the sampling inaccuracy varies between undersampling and oversampling texels resulting in variable image quality. In a perspective display, a square pixel footprint can map into a rectangle in texture space. For extreme perspective views, many texels sometimes map into a single pixel footprint A.
Supersampling techniques have been developed to improve the texture detail which is mapped to a pixel footprint area. In so-called regular supersampling, an image is sampled n times the display resolution to improve the texture display quality (see FIG. 1B, n=9 adapted from Wolberg at page 169). Irregular supersampling techniques take samples at non-uniform sampling locations to further reduce aliasing artifacts which can arise when texture samples are regularly-spaced. See, e.g, the discussion of irregular sampling techniques such as stochastic sampling including Poisson sampling, jittered sampling, and point-diffusion sampling, in Wolberg, pp. 173-177. Regular and irregular supersampling techniques, however, have been inefficient and unworkable for real-time display of special effects images. Computational costs and delays quickly become prohibitive, especially when images are distorted, rotated, warped, or displayed in perspective.
The degree of supersampling is often determined based on a global consideration of the texture detail needed in a display image. For example, a regular supersampling grid as shown in FIG. 1B is often applied over an entire display regardless of any local pixel footprint orientation and shape when mapped in texture space. This is costly and inefficient. The regular samples can also create aliasing artifacts. Proposals for adjusting supersampling density locally, however, appear to be too costly and/or slow to provide texture in real-time for video special effects. See, the discussion by Wolberg regarding adaptive stochastic sampling in section 6.3.5, page 177 (referring to work by M. Dippe) and uniform supersampling based on a single compression or area value in section 6.4.4, page 179 (referring to work by Gangnet et al.).
Perny et al. uses per-pixel supersampling of texture based on the area of the pixel footprint in texture space. Each subsample is a bilinear interpolation of the four nearest texels. A single user-defined oversampling coefficient "S" and compression ratio A are used to control a mesh size, and thereby, jointly reduce sampling rates in X and Y. See Perny et al., "Perspective Mapping of Planar Textures," Computer Graphics, Vol. 16, No. 1, May 1982, pp. 70-100 and Gangnet et al., "Perspective Mapping of Planar Textures," Eurographics '82 Proceedings, pp. 57-71.
An efficient supersampling texture mapping approximation has also not been applied to pre-filtered multi-resolutional texture data. For example, MIP-mapping, involves pre-filtering a texture map at progressively coarser resolutions to form a set of multi-resolution level-of-detail (LOD) maps, also called an "image pyramid" or "MIP-map." To map texture to a pixel footprint, a square texel from a particular map having the most appropriate level of detail is chosen.
In the system of Dungan et al. an image pyramid is used to reduce the integration approximation for a pixel footprint in texture space to a few lookups in a reduced resolution image (LOG image). The LOD image chosen for a pixel is based on the average of the footprint width and height. As a result, a texture may be underfiltered in one dimension and overfiltered in another dimension. The entire screen is uniformly supersampled at a 2.times.2 rate to minimize undersampling artifacts. See, Dungan et al., "Texture Tile Considerations for Raster Graphics," Siggraph '78 Proceedings (1978), pp. 130-134.
L. Williams further describes blending between two nearest LOD images to approximate footprint size. Bilinear interpolation is used to position the footprint. See, Williams, L., "Pyramidal Parametrics," Siggraph '83 Proceedings, (1983), pp. 1-11. This technique essentially approximates a pixel's parallelogram footprint in texture space to a pre-filtered square texel. This produces an excessively blurry image due to oversampling and does not adjust for rotation. These drawbacks become especially pronounced in special effects computer graphics applications where an object is rotated, warped, or displayed in perspective.
What is needed is a texture supersampling algorithm for multi-resolutional texture data which efficiently approximates an arbitrary pixel footprint (shape and orientation) during texture mapping and displays high-quality special effects texture detail in real-time. Rich texture detail needs to be applied in real-time to video images even for warped, rotated, perspective, and/or distorted images. Two-dimensional and three-dimensional multi-resolutional texture data need to be accommodated.